The widespread use of multimedia content, multimedia security and digital rights management have become very important issues. A straightforward approach to protect multimedia data is using the traditional encryption methods such as the Advanced Encryption Standard (AES) and Data Encryption Standard (DES) encryptions to encrypt the entire data. Nevertheless, encryption of multimedia files has to be carried out carefully. On one hand, encrypting and decrypting compressed multimedia files cause excessive computational burden and power consumption at the encoder and decoder and hence the server and transcoder. More importantly, compressed multimedia files typically have well-defined hierarchical structures that can be exploited using many techniques such as scalability, transcoding, and rate shaping. However, these structures are no longer recognizable once the data are encrypted.
In cryptography, ciphertext is the result of the encryption process that transforms original unencrypted information (commonly called plaintext) using cipher to make it unreadable to anyone except those possessing special knowledge (usually referred to as a key).
A cryptographic attack is a method for circumventing the security of a cryptographic system by finding a weakness in a code, cipher, cryptographic protocol or key management scheme. This process is also called “cryptanalysis”. In cryptanalysis, the most common cryptographic attacks include chose-plain text attack and chose-ciphertext attack. A chosen-plaintext attack is an attack model for cryptanalysis that presumes that an attacker has the capability of choosing arbitrary plaintext to be encrypted and obtaining the corresponding ciphertext. The goal of the attack is to gain some further information that reduces the security of the encryption scheme. In the worst case, a chosen-plaintext attack could reveal the scheme's secret key. A chosen-ciphertext attack is an attack model for cryptanalysis in which the attacker gathers information, at least in part, by choosing a ciphertext and obtaining its decryption under an unknown key.
The recent trend in multimedia encryption has drawn more attention to integrating encryption and compression by introducing randomness into the entropy coder such as the Huffman coder and arithmetic coder. These encryption schemes employ joint encryption-compression approaches where encryption and compression can be achieved in one single step. In C. Wu and C. C. J. Kuo “Design of integrated multimedia compression and encryption systems,” IEEE Transactions on Multimedia, vol. 7, pp. 828-839, October 2005, a Multiple Huffman Tree (MHT) technique encrypts the information by alternately using different Huffman trees in a secret order, without influencing the coding efficiency. This technique, however, is vulnerable to chosen-plaintext attacks as shown in J. Zhou, Z. Liang, Y. Chen, and O. C. Au “Security analysis of multimedia encryption schemes based on multiple Huffman table,” IEEE Signal Processing Letters, vol. 14, no. 3, pp. 201-204, March 2007 (hereinafter “Zhou”), which is hereby incorporated by reference.
Compared with the Huffman coding, the arithmetic coding (AC) is capable of offering higher coding efficiency, and thus is becoming more and more popular in the new generation of data compression standards such as JPEG 2000 and H.264.
In M. Grangetto, E. Magli, and G. Olmo “Multimedia selective encryption by means of randomized arithmetic coding,” IEEE Transactions on Multimedia, vol. 8, pp. 905-917, October 2006, an efficient encryption scheme based on AC randomly swaps the least probable symbol (LPS) and the most probably symbol (MPS) within the coding interval.
In R. Bose and S. Pathak “A novel compression and encryption scheme using variable model arithmetic coding and couple chaotic system,” IEEE Transactions on Circuits and Systems I, vol. 53, pp. 848-857, April, 2006, an encryption technique has a variable model arithmetic coder integrated with a coupled chaotic system.
More recently, in H. Kim, J. T. Wen, and J. D. Villasenor “Secure arithmetic coding,” IEEE Transactions on Signal Processing, vol. 55, pp. 2263-2272, May 2007, a secure arithmetic coding (SAC) system is described, which is claimed to be both secure and efficient. This technique, however, is subject to the chosen-ciphertext attack.
In data compression, a prefix code is a code system, typically a variable-length code, with the “prefix property,” meaning that there is no valid code word in the system that is a prefix (start) of any other valid code word in the set. For example, a code with code words {9, 59, 55} has the prefix property, whereas a code consisting of {9, 5, 59, 55} does not, because “5” is a prefix of both “59” and “55”. With a prefix code, a decoder/receiver can tell the end of a codeword without using a special marker.
A universal code is a prefix code that maps positive integers to their corresponding binary codewords. For a universal code, no matter what the true probability distribution of the integers is, as long as the distribution is monotonic (i.e., p(i)≧p(i+1) for all positive integer i), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that source probability distribution would have assigned. That is, given an arbitrary source with nonzero entropy, a universal code achieves average codeword length, which is at most a constant times the optimal possible for that source. Typical universal codes include Elias gamma coding, Elias delta coding, Elias omega coding, Fibonacci coding, Levenstein coding, and Exp-Golomb coding. In particular, Elias gamma coding is a special case of the Exp-Golomb coding which is currently used in the H.264/MPEG-4 AVC video coding standard.
In order to improve the security of the universal codes, efforts have been made to combine coding with data encryption. For example, S. Lian et al. “Secure advanced video coding based on selective encryption algorithms,” IEEE Tran. Consumer Electronics, vol. 52, no. 2, pp. 621-629, May 2006 (hereinafter “Lian”), describes an Exp-Golomb encryption algorithm (EGEA) as illustrated in FIG. 1. Each Exp-Golomb codeword has a form 00 . . . 01Y having a series of R leading zeros, one “1”-bit separator, and R bits of information Y. Let S be an input symbol to be encoded. According to Lian, the encoding process of EGEA is described as follows:
Step 1: encoding symbol S into codeword Y using the regular Exp-Golomb coding; and
Step 2: performing an logic exclusive-or (XOR) operation on the codeword Y and a key stream K: Z=Y⊕K.
Therefore, the resulting codeword has the form of 00 . . . 01Z with R bits of leading zeros, one bit of “1” representing the separator, and R bits of encrypted information Z. However, it should be noted that it is still unclear how the codeword “1” should be treated in Lian's encryption technique. In other words, according to Lian, one would not know whether the XOR operation should be performed when the codeword “1” is encountered. In fact, no matter whether the XOR operation is performed on the codeword “1,” the coding technique described by Lian has serious problems.
In particular, if the XOR operation is not performed on the codeword “1,” in the bit stream generated according to Lian's technique, it is not difficult to determine the boundary of different codewords. Because “1” is not encrypted using the key stream K, one can immediately recover the corresponding symbols. Because the codeword length of “1” is 1, one can roughly estimate the probability of the symbols associated with “1” as 2−1. Therefore, in this case, an attacker can recover half of the symbols by only observing the ciphertext (ciphertext-only attack).
If, on the other hand, the XOR operation is performed on the codeword “1.” In this case, the codeword “1” may be flipped to “0,” depending on the key stream, which cannot be discriminated from the leading “0s.” This may lead to the decoding failure. For example, the symbol sequence to be encoded is a0a4a1, and the key stream is 101010. Hence, the encoded bit stream is 000100010. However, if the symbol sequence to be encoded is a12a0a0, it is not difficult to verify that the encoded bit stream is also 000100010. Therefore, on the decoder side, it is impossible to distinguish the correct symbol sequence from which the codewords were obtained.
Therefore, it is desired to design an encryption technique for universal codes that is secure under both ciphertext and plaintext attacks. It is also desired to design an encryption technique for universal codes that minimize decoding errors.